package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 12/10/20 2:37 PM
 *
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 */
public class _5_最长回文子串 {

    public String longestPalindrome(String s) {

        if (s == null) {

            return null;
        }

        if (s.length() == 1) {

            return s;
        }

        char[] sChar = s.toCharArray();

        int[][]dp = new int[s.length()][s.length()];

        int index=0,len = 1;

        for (int i = sChar.length - 2; i >=0; i--) {

            dp[i][i] = 1;
            for (int j = i+1; j < sChar.length ; j++) {

                if (sChar[j] == sChar[i]) {
                    int dis = j - i + 1;
                    if (dis == 2) {

                        dp[i][j] = 1;

                        if (len < dis) {
                            len = 2;
                            index = i;
                        }
                    }else {

                        if (dp[i+1][j-1] == 1) {

                            dp[i][j] = 1;

                            if (len < dis) {

                                len = dis;
                                index = i;
                            }

                        }
                    }
                }
            }
        }


        for (int i = 0; i < sChar.length; i++) {

            System.out.println(Arrays.toString(dp[i]));

        }

        return s.substring(index,index+len);
    }
}
